package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Administrator
 * @description 课程表 II
 * @date 2023/3/23 0023
 */
public class Solution210 {
    // 记录一次 traverse 递归经过的节点
    boolean[] onPath;
    // 记录遍历过的节点，防止走回头路
    boolean[] visited;
    // 记录图中是否有环
    boolean hasCycle = false;
    // 记录后序遍历结果
    List<Integer> postorder = new ArrayList<>();
    // 图
    List<Integer>[] graph;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        graph = buildGraph(numCourses, prerequisites);
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            traverse(i);
        }
        if (hasCycle){
            return new int[]{};
        }
        // 将后序遍历结果反转，转化成 int[] 类型
        Collections.reverse(postorder);
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = postorder.get(i);
        }
        return res;
    }

    private void traverse(int s) {
        if (onPath[s]){
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }

        visited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(t);
        }
        onPath[s] = false;
        // 后序遍历位置
        postorder.add(s);
    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        // 图中共有 numCourses 个节点
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : prerequisites) {
            // 修完课程 from 才能修课程 to
            graph[edge[1]].add(edge[0]);
        }
        return graph;
    }
}
